{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab 3: Bayes Classifier and Boosting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Jupyter notebooks\n",
    "\n",
    "In this lab, you can use Jupyter <https://jupyter.org/> to get a nice layout of your code and plots in one document. However, you may also use Python as usual, without Jupyter.\n",
    "\n",
    "If you have Python and pip, you can install Jupyter with `sudo pip install jupyter`. Otherwise you can follow the instruction on <http://jupyter.readthedocs.org/en/latest/install.html>.\n",
    "\n",
    "And that is everything you need! Now use a terminal to go into the folder with the provided lab files. Then run `jupyter notebook` to start a session in that folder. Click `lab3.ipynb` in the browser window that appeared to start this very notebook. You should click on the cells in order and either press `ctrl+enter` or `run cell` in the toolbar above to evaluate all the expressions.\n",
    "\n",
    "Be sure to put `%matplotlib inline` at the top of every code cell where you call plotting functions to get the resulting plots inside the document."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Import the libraries\n",
    "\n",
    "In Jupyter, select the cell below and press `ctrl + enter` to import the needed libraries.\n",
    "Check out `labfuns.py` if you are interested in the details."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from scipy import misc\n",
    "from imp import reload\n",
    "from labfuns import *\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bayes classifier functions to implement\n",
    "\n",
    "The lab descriptions state what each function should do."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# NOTE: you do not need to handle the W argument for this part!\n",
    "# in: labels - N vector of class labels\n",
    "# out: prior - C x 1 vector of class priors\n",
    "def computePrior(labels, W=None):\n",
    "    Npts = labels.shape[0]\n",
    "    if W is None:\n",
    "        W = np.ones((Npts,1))/Npts\n",
    "    else:\n",
    "        assert(W.shape[0] == Npts)\n",
    "    classes = np.unique(labels)\n",
    "    Nclasses = np.size(classes)\n",
    "\n",
    "    prior = np.zeros((Nclasses,1))\n",
    "\n",
    "    # TODO: compute the values of prior for each class!\n",
    "    # ==========================\n",
    "    \n",
    "    # ==========================\n",
    "\n",
    "    return prior\n",
    "\n",
    "# NOTE: you do not need to handle the W argument for this part!\n",
    "# in:      X - N x d matrix of N data points\n",
    "#     labels - N vector of class labels\n",
    "# out:    mu - C x d matrix of class means (mu[i] - class i mean)\n",
    "#      sigma - C x d x d matrix of class covariances (sigma[i] - class i sigma)\n",
    "def mlParams(X, labels, W=None):\n",
    "    assert(X.shape[0]==labels.shape[0])\n",
    "    Npts,Ndims = np.shape(X)\n",
    "    classes = np.unique(labels)\n",
    "    Nclasses = np.size(classes)\n",
    "\n",
    "    if W is None:\n",
    "        W = np.ones((Npts,1))/float(Npts)\n",
    "\n",
    "    mu = np.zeros((Nclasses,Ndims))\n",
    "    sigma = np.zeros((Nclasses,Ndims,Ndims))\n",
    "\n",
    "    # TODO: fill in the code to compute mu and sigma!\n",
    "    # ==========================\n",
    "    \n",
    "    # ==========================\n",
    "\n",
    "    return mu, sigma\n",
    "\n",
    "# in:      X - N x d matrix of M data points\n",
    "#      prior - C x 1 matrix of class priors\n",
    "#         mu - C x d matrix of class means (mu[i] - class i mean)\n",
    "#      sigma - C x d x d matrix of class covariances (sigma[i] - class i sigma)\n",
    "# out:     h - N vector of class predictions for test points\n",
    "def classifyBayes(X, prior, mu, sigma):\n",
    "\n",
    "    Npts = X.shape[0]\n",
    "    Nclasses,Ndims = np.shape(mu)\n",
    "    logProb = np.zeros((Nclasses, Npts))\n",
    "\n",
    "    # TODO: fill in the code to compute the log posterior logProb!\n",
    "    # ==========================\n",
    "    \n",
    "    # ==========================\n",
    "    \n",
    "    # one possible way of finding max a-posteriori once\n",
    "    # you have computed the log posterior\n",
    "    h = np.argmax(logProb,axis=0)\n",
    "    return h"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The implemented functions can now be summarized into the `BayesClassifier` class, which we will use later to test the classifier, no need to add anything else here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# NOTE: no need to touch this\n",
    "class BayesClassifier(object):\n",
    "    def __init__(self):\n",
    "        self.trained = False\n",
    "\n",
    "    def trainClassifier(self, X, labels, W=None):\n",
    "        rtn = BayesClassifier()\n",
    "        rtn.prior = computePrior(labels, W)\n",
    "        rtn.mu, rtn.sigma = mlParams(X, labels, W)\n",
    "        rtn.trained = True\n",
    "        return rtn\n",
    "\n",
    "    def classify(self, X):\n",
    "        return classifyBayes(X, self.prior, self.mu, self.sigma)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test the Maximum Likelihood estimates\n",
    "\n",
    "Call `genBlobs` and `plotGaussian` to verify your estimates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "X, labels = genBlobs(centers=5)\n",
    "mu, sigma = mlParams(X,labels)\n",
    "plotGaussian(X,labels,mu,sigma)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Call the `testClassifier` and `plotBoundary` functions for this part."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "testClassifier(BayesClassifier(), dataset='iris', split=0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "testClassifier(BayesClassifier(), dataset='vowel', split=0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "plotBoundary(BayesClassifier(), dataset='iris',split=0.7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Boosting functions to implement\n",
    "\n",
    "The lab descriptions state what each function should do."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# in: base_classifier - a classifier of the type that we will boost, e.g. BayesClassifier\n",
    "#                   X - N x d matrix of N data points\n",
    "#              labels - N vector of class labels\n",
    "#                   T - number of boosting iterations\n",
    "# out:    classifiers - (maximum) length T Python list of trained classifiers\n",
    "#              alphas - (maximum) length T Python list of vote weights\n",
    "def trainBoost(base_classifier, X, labels, T=10):\n",
    "    # these will come in handy later on\n",
    "    Npts,Ndims = np.shape(X)\n",
    "\n",
    "    classifiers = [] # append new classifiers to this list\n",
    "    alphas = [] # append the vote weight of the classifiers to this list\n",
    "\n",
    "    # The weights for the first iteration\n",
    "    wCur = np.ones((Npts,1))/float(Npts)\n",
    "\n",
    "    for i_iter in range(0, T):\n",
    "        # a new classifier can be trained like this, given the current weights\n",
    "        classifiers.append(base_classifier.trainClassifier(X, labels, wCur))\n",
    "\n",
    "        # do classification for each point\n",
    "        vote = classifiers[-1].classify(X)\n",
    "\n",
    "        # TODO: Fill in the rest, construct the alphas etc.\n",
    "        # ==========================\n",
    "        \n",
    "        # alphas.append(alpha) # you will need to append the new alpha\n",
    "        # ==========================\n",
    "        \n",
    "    return classifiers, alphas\n",
    "\n",
    "# in:       X - N x d matrix of N data points\n",
    "# classifiers - (maximum) length T Python list of trained classifiers as above\n",
    "#      alphas - (maximum) length T Python list of vote weights\n",
    "#    Nclasses - the number of different classes\n",
    "# out:  yPred - N vector of class predictions for test points\n",
    "def classifyBoost(X, classifiers, alphas, Nclasses):\n",
    "    Npts = X.shape[0]\n",
    "    Ncomps = len(classifiers)\n",
    "\n",
    "    # if we only have one classifier, we may just classify directly\n",
    "    if Ncomps == 1:\n",
    "        return classifiers[0].classify(X)\n",
    "    else:\n",
    "        votes = np.zeros((Npts,Nclasses))\n",
    "\n",
    "        # TODO: implement classificiation when we have trained several classifiers!\n",
    "        # here we can do it by filling in the votes vector with weighted votes\n",
    "        # ==========================\n",
    "        \n",
    "        # ==========================\n",
    "\n",
    "        # one way to compute yPred after accumulating the votes\n",
    "        return np.argmax(votes,axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The implemented functions can now be summarized another classifer, the `BoostClassifier` class. This class enables boosting different types of classifiers by initializing it with the `base_classifier` argument. No need to add anything here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# NOTE: no need to touch this\n",
    "class BoostClassifier(object):\n",
    "    def __init__(self, base_classifier, T=10):\n",
    "        self.base_classifier = base_classifier\n",
    "        self.T = T\n",
    "        self.trained = False\n",
    "\n",
    "    def trainClassifier(self, X, labels):\n",
    "        rtn = BoostClassifier(self.base_classifier, self.T)\n",
    "        rtn.nbr_classes = np.size(np.unique(labels))\n",
    "        rtn.classifiers, rtn.alphas = trainBoost(self.base_classifier, X, labels, self.T)\n",
    "        rtn.trained = True\n",
    "        return rtn\n",
    "\n",
    "    def classify(self, X):\n",
    "        return classifyBoost(X, self.classifiers, self.alphas, self.nbr_classes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Run some experiments\n",
    "\n",
    "Call the `testClassifier` and `plotBoundary` functions for this part."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "testClassifier(BoostClassifier(BayesClassifier(), T=10), dataset='iris',split=0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "testClassifier(BoostClassifier(BayesClassifier(), T=10), dataset='vowel',split=0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "plotBoundary(BoostClassifier(BayesClassifier()), dataset='iris',split=0.7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now repeat the steps with a decision tree classifier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "testClassifier(DecisionTreeClassifier(), dataset='iris', split=0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "testClassifier(BoostClassifier(DecisionTreeClassifier(), T=10), dataset='iris',split=0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "testClassifier(DecisionTreeClassifier(), dataset='vowel',split=0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "testClassifier(BoostClassifier(DecisionTreeClassifier(), T=10), dataset='vowel',split=0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "plotBoundary(DecisionTreeClassifier(), dataset='iris',split=0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "plotBoundary(BoostClassifier(DecisionTreeClassifier(), T=10), dataset='iris',split=0.7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bonus: Visualize faces classified using boosted decision trees\n",
    "\n",
    "Note that this part of the assignment is completely voluntary! First, let's check how a boosted decision tree classifier performs on the olivetti data. Note that we need to reduce the dimension a bit using PCA, as the original dimension of the image vectors is `64 x 64 = 4096` elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "testClassifier(BayesClassifier(), dataset='olivetti',split=0.7, dim=20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "testClassifier(BoostClassifier(DecisionTreeClassifier(), T=10), dataset='olivetti',split=0.7, dim=20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should get an accuracy around 70%. If you wish, you can compare this with using pure decision trees or a boosted bayes classifier. Not too bad, now let's try and classify a face as belonging to one of 40 persons!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "X,y,pcadim = fetchDataset('olivetti') # fetch the olivetti data\n",
    "xTr,yTr,xTe,yTe,trIdx,teIdx = trteSplitEven(X,y,0.7) # split into training and testing\n",
    "pca = decomposition.PCA(n_components=20) # use PCA to reduce the dimension to 20\n",
    "pca.fit(xTr) # use training data to fit the transform\n",
    "xTrpca = pca.transform(xTr) # apply on training data\n",
    "xTepca = pca.transform(xTe) # apply on test data\n",
    "# use our pre-defined decision tree classifier together with the implemented\n",
    "# boosting to classify data points in the training data\n",
    "classifier = BoostClassifier(DecisionTreeClassifier(), T=10).trainClassifier(xTrpca, yTr)\n",
    "yPr = classifier.classify(xTepca)\n",
    "# choose a test point to visualize\n",
    "testind = random.randint(0, xTe.shape[0]-1)\n",
    "# visualize the test point together with the training points used to train\n",
    "# the class that the test point was classified to belong to\n",
    "visualizeOlivettiVectors(xTr[yTr == yPr[testind],:], xTe[testind,:])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
